Skip to main content

Kth from End of Linked List

Problem Description​

Given the head of a linked list and a number k, your task is to find the kth node from the end. If k is more than the number of nodes, then the output should be -1.

Examples​

Example 1:

Input:
n = 5, k = 2
value[] = [1, 2, 3, 4, 5]
Output: 4
Explanation: The 2nd node from the end is 4.

Example 2:

Input:
n = 3, k = 4
value[] = [10, 20, 30]
Output: -1
Explanation: There are only 3 nodes in the linked list, so the 4th node from the end does not exist.

Your Task​

You don't need to read input or print anything. Your task is to complete the function getKthFromLast() which takes the head of the linked list and k as input parameters and returns the data of the kth node from the end of the linked list.

Expected Time Complexity: O(N)O(N)

Expected Auxiliary Space: O(1)O(1)

Constraints​

  • 1 ≤ n ≤ 10^5
  • 1 ≤ value[i] ≤ 10^7
  • 1 ≤ k ≤ 10^5

Problem Explanation​

The task is to find the kth node from the end of a linked list. If k is greater than the number of nodes in the list, return -1.

Code Implementation​

Written by @arunimad6yuq
class ListNode:
def __init__(self, x):
self.val = x
self.next = None

class Solution:
def getKthFromLast(self, head: ListNode, k: int) -> int:
fast = slow = head
for _ in range(k):
if not fast:
return -1
fast = fast.next

while fast:
slow = slow.next
fast = fast.next

return slow.val if slow else -1

# Example usage
if __name__ == "__main__":
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
solution = Solution()
print(solution.getKthFromLast(head, 2)) # Expected output: 4

Example Walkthrough​

Example 1:

For the linked list:

1 -> 2 -> 3 -> 4 -> 5
  1. The 2nd node from the end is 4.

Example 2:

For the linked list:

10 -> 20 -> 30
  1. There are only 3 nodes in the linked list, so the 4th node from the end does not exist, thus the output is -1.

Solution Logic:​

  1. Use two pointers fast and slow.
  2. Move fast pointer k steps ahead.
  3. Move both pointers until fast reaches the end.
  4. The slow pointer will be at the kth node from the end.
  5. Return the value of the slow pointer or -1 if k is greater than the number of nodes.

Time Complexity​

  • The function traverses the linked list once, so the time complexity is O(N)O(N).

Space Complexity​

  • The function uses constant space, so the auxiliary space complexity is O(1)O(1).

References​